import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] array ={2,3,4,1,2,3,4,5,4,3,2,1,45};
        new QuickSort().quicksort(array, 0, array.length-1);
        System.out.println(Arrays.toString(array));
    }

    void quicksort(int[] array,int low,int high){
        //结束条件
        if(low>=high) return;
        //基准
        int base=array[low];
        int i=low,j=high;
        //必须先排右边,因为停止的位置要被换到开头，必须小于base
        // 这是因为外层循环到最后一次时
        //第一层循环结束的条件是 array[j]>=base 不成立
        //第二层循环结束的条件是 i<j 不成立（i=j）
        //这意味着停下来的时候，array[i]<base,此时swap,能满足我们要求选到的新base，左边全小于base，右边全大于base
        //那如果反过来，则意味着跳出外层循环的时候array[i]>base,此时这个要求就不能满足
        while(i<j){
            while(array[j]>=base && i<j){
                j--;
            }
            while(array[i]<=base && i<j){
                i++;
            }
            swap(array,i,j);
        }
        swap(array,low,i);
        quicksort(array, low, i-1);
        quicksort(array, i+1, high);
    }

    void swap(int[] array,int i,int j){
        int key = array[i];
        array[i]=array[j];
        array[j]=key;
    }
}
